Problemi del Calcolo Combinatorio

Cenni al Calcolo Combinatorio, definizione del coefficiente binomiale , problemi misti del Calcolo Combinatorio, teorema di Newton (o del binomio).


Problemi del Calcolo Combinatorio

Significato del calcolo combinatorio; quali problemi esso mira di risolvere. Alcuni problemi: disposizioni con ripetizioni, disposizione di oggetti a m a m, permutazioni di n oggetti e combinazioni. Alcuni problemi misti del calcolo combinatorio


1. Cosa vuol dire "calcolo combinatorio"

Se si definisce l'insieme dei numeri naturali come l'insieme dei numeri che servono per contare, allora il calcolo combinatorio si basa sul problema di contare certi insiemi/oggetti/

DEF 1. Cardinalità Si definisce la cardinalità di un insieme come il numero degli elementi contenuti nell'insieme . Lo si denota come .

2. I problemi del calcolo combinatorio

Il calcolo combinatorio ci presenta vari problemi che valgono la pena di essere studiati.

PROBLEMA 2.1. Cardinalità del prodotto cartesiano

PROBLEMA 2.1. Supponiamo che , , ove sono insiemi e . Allora ci poniamo il problema di trovare .
Se disegniamo il grafico di un qualsiasi prodotto cartesiano , si evince che per ogni riga ci sono colonne; quindi
Pasted image 20231004223727.png

PROBLEMA 2.2. Disposizioni con ripetizione

PROBLEMA 2.2. Siano insiemi con ; voglio contare il numero degli elementi di Per risolvere questo problema si può avvalere del diagramma in cui rappresentiamo gli due insiemi . Ora, prendendo il primo elemento , vediamo che possiamo definire funzioni, collegando l'elemento a .
Stesso discorso vale per ; quindi generalizzando possiamo vedere che il risultato viene

DEF 2.2. Questo problema, nel calcolo combinatorio, si chiama disposizioni con ripetizioni, ovvero senza vincoli particolari.

Pasted image 20231004223802.png

ESEMPIO 2.2.1.

Se voglio costruire tutte le bandiere tricolori possibili (ove sono ammessi i anche colori ripetuti) con 4 colori a disposizione, quante posso costruirne?
SOLUZIONE. Questo è un caso applicato di disposizioni con ripetizione; infatti se si definisce le caselle delle bandiere come un insieme a tre variabili, , allora vogliamo trovare tutte le funzioni associate da a
Pertanto la soluzione è .

PROBLEMA 2.3. Disposizioni di oggetti da a

PROBLEMA 2.3. Prendiamo lo stesso problema di prima; tuttavia vogliamo ora considerare un vincolo particolare: vogliamo cercare solo le funzioni iniettive (DEF 3.2.) da a . Ricapitolando, per iniettiva si intende che ad ogni , vengono associati immagini diversi. Pertanto, è necessario che .
DEF 2.3.1. Inoltre indichiamo l'insieme delle funzioni iniettive come .
SOLUZIONE. Si può avvalere dello stesso grafico di prima; se prendo il primo elemento , allora ho scelte per lo stesso ragionamento di prima; ora, se prendo il secondo elemento , allora per rispettare il vincolo, ho una scelta in meno (ovvero l'elemento associato ad ): quindi ora ho scelte. Procedendo avanti così, arrivo fino all'elemento per cui ho scelte.
Pertanto

ESEMPIO 2.3.1.

Prendiamo in esame lo stesso problema di prima, ovvero quella avendo a disposizione una bandiera tricolore da colorare e quattro colori.
Ora non vogliamo più i stessi colori; infatti, se la funzione dev'essere iniettiva, allora in un senso applicato ciò vuol dire che ad ogni area della bandiera dev'esserci un colore diverso.
Quindi si tratta di calcolare

PROBLEMA 2.4. Permutazioni

PROBLEMA 2.4. Prendiamo il problema appena preso in esame (ovvero la disposizione di oggetti da a ) e ora vogliamo ci aggiungiamo un ulteriore vincolo: cerchiamo le funzioni biiettive, ovvero quelle sia iniettive che suriettive. Da qui consegue necessariamente che .
DEF 2.4.1. Definiamo l'insieme delle permutazioni (ovvero delle funzioni biiettive) come .
SOLUZIONE. Questo non è altro che un caso speciale di ove , quindi

ESEMPIO 2.4.1.

Consideriamo un problema totalmente diverso; se ho la stringa "CIAO", quante volte posso cambiarlo in modo tale che le lettere presenti nella stringa ci siano comunque?
Questo si tratta ovviamente di una permutazione, quindi calcoliamo .

PROBLEMA 2.5. Combinazioni, coefficienti binomiali

PROBLEMA 2.5. Se considero un insieme con , e un numero tale che , allora voglio calcolare il numero di sottoinsiemi di con elementi.
DEF. 2.5.1. Definiamo l'insieme dei sottoinsiemi di con elementi come e si legge come " su ". Inoltre lo si chiama anche come il coefficiente binomiale oppure le combinazioni di oggetti a a .
SOLUZIONE. Qui usiamo un esperimento mentale che presenta una situazione analoga a quella presentata.
Suppongo di aver numero di palline, da cui voglio scegliere ; per la prima pallina posso sceglierne , poi per la pallina posso sceglierne , poi andando così finche si raggiunge l'ultima pallina da cui posso scegliere . Si osserva che questo è esattamente le disposizioni da a , .
Tuttavia in questo modo tengo conto dell'ordine in cui scelgo le palline; invece le combinazioni non tengo conto dell'ordine. Quindi se vogliamo considerare l'ordine, dobbiamo attribuire ad ogni combinazione una permutazione; ciò vuol dire che bisogna moltiplicare le combinazioni di oggetti a a per le permutazioni di oggetti; pertanto si scriveda cui deriva Nella pagina Coefficiente Binomiale ci soffermeremo particolare (appunto) sul coefficiente binomiale, in quanto essa porta con sé delle proprietà particolari che ci permetteranno di costruire certi oggetti matematici, tra cui il triangolo di Tartaglia.

ESEMPIO 2.5.1.

Se ho un sacco con palline da cui ne estraggo , quante combinazioni possibili ho?
Semplicemente, .

3. Esempi misti del Calcolo Combinatorio

Ora presentiamo alcuni esempi misti del calcolo combinatorio, che può comprendere l'ausilio di alcune delle definizioni date sopra e un buon approccio critico ai problemi.

PROBLEMA 3.1. Ho un mazzo da carte e ne pesco ; quanti sono i possibili risultati ?
Questo è un caso quasi-banale di combinazioni, quindi PROBLEMA 3.1.A Ora considerando che ci sono semi (quindi carte per seme), quanti sono i risultati che NON contengono le carte di denari?
Anche qui si tratta di un problema di combinazioni, che però va affrontato più criticamente: infatti vogliamo estrarre le carte escludendone , in quanto essi rappresentano dei semi; quindi sostanzialmente il "corpo" delle carte sono solo .

PROBLEMA 3.1.B Considerando lo stesso mazzo di carte, ora voglio invece calcolare i risultati che contengono invece i denari.
Un approccio particolarmente furbo è quello semplicemente di prendere (ovvero tutte le combinazioni possibili) e sottrarli per il numero dei risultati senza i denari; infatti l'insieme dei risultati con i denari è complemento dell'insieme dei risultati senza i denari.
Quindi, Oppure un altro approccio comunque accettabile è di considerare tutte le combinazioni dei risultati con esattamente un seme, poi due semi e infine tre semi e infine sommarli.
Infatti,

PROBLEMA 3.2. Il Lotto. Ho bussolotti, ovvero dei numeri; ne estraggo . Quali sono le possibili estrazioni?
Anche qui si tratta di un caso di combinazioni in quanto non tiene conto dell'ordine dei numeri estratti (in quanto essi vengono già ordinati in un'ordine crescente). PROBLEMA 3.3. Ho una scacchiera e pedine uguali.
In quanti modi posso mettere le pedine sulla scacchiera, se voglio che tutte le righe e tutte le colonne abbiano almeno una pedina?

Soluzione controllata con D.D.S.: Parzialmente corretta ma manca un pezzo.

PROPOSTA DELLA SOLUZIONE. Ragioniamo nel seguente modo:

  1. Voglio porre le prime pedine in modo tale che il vincolo venga rispettato (quindi tutte le righe e le colonne hanno almeno una pedina piazzata), poi per porre la -esima pedina liberamente.
  2. Per le pedine ragiono così:
    1. Voglio porre la prima pedina sulla prima riga e su qualsiasi colonna. Ho quindi possibilità.
    2. Ora voglio porre la seconda pedina sulla seconda riga; però non posso porlo sulla stessa colonna scelta dalla prima pedina, dandomi una scelta in meno. Ho quindi possibilità.
    3. Mi accorgo che qui si tratta di un semplice problema di permutazioni (o disposizioni di oggetti a 5 a 5), ovvero che per calcolare tutte le possibilità devo fare .
  3. Ora considero la -esima pedina: se le altre pedine hanno già occupato le loro caselle, allora mi rimangono solo caselle ().
  4. Quindi ottengo il risultato

Coefficiente Binomiale

Coefficiente Binomiale
Coefficiente Binomiale

Coefficiente binomiale come strumento per risolvere un problema del calcolo combinatorio; regole e teoremi sul coefficiente binomiale; costruzione del triangolo di Tartaglia; teorema di Newton (o del binomio) con dimostrazione. Applicazioni del teorema.


1. Coefficiente Binomiale

2. Proprietà del coefficiente binomiale

Enunciamo le seguenti proprietà del coefficiente binomiale :

  1. REGOLA DI STIFEL. Sia , DIMOSTRAZIONE FORMALE.
    Per definizione, Osservare la proprietà che consegue dalla definizione ricorrente del fattoriale (Assiomi di Peano, il principio di induzione): da ciò implica che Quindi secondo questa logica, si può dire le seguenti: Allora DIMOSTRAZIONE SENZA CALCOLI/TEORICA.
    Alternativamente, si potrebbe pensare la regola di Stifel nel seguente modo:
    "Voglio contare le contare i sottoinsiemi con elementi dell'insieme (ove ); quindi voglio .
    Ora distinguiamo uno degli elementi di con un contrassegno particolare, come il colore rosso; adesso gli insiemi di elementi si dividono in due.
    Ovvero, l'insieme dei sottoinsiemi che contengono l'elemento rosso e l'insieme dei sottoinsiemi che non contengono l'elemento rosso.
    Consideriamo l'insieme di tutti i sottoinsiemi che contengono l'elemento speciale: devo quindi obbligatoriamente considerare l'elemento rosso, tirandolo fuori. Ho quindi da elementi ne posso scegliere solo , in quanto una è stata già scelta, e posso scegliere solo elementi visto che il primo elemento (ovvero il rosso) è stato già obbligatoriamente scelto.
    Consideriamo invece l'altro insieme di tutti i sottoinsiemi che NON contengono l'elemento contrassegnato: in questo caso si tratta semplicemente di escludere l'elemento rosso dalle scelte possibili, dandoci solo scelte su .
    Pertanto

3. Costruzione del triangolo di Tartaglia

Enunciamo di nuovo le 3 regole sopra: Da queste tre proprietà possiamo rappresentare i coefficienti binomiali tramite il c.d. triangolo di Tartaglia

3.1. Triangolo di Tartaglia

Disponiamo tutti i coefficienti binomiali , dove la "colonna" (a partire dall'alto) rappresenta il numero e dove la "riga" (a partire da sx.) rappresenta il numero . Ad ogni riga rappresentiamo tutti i coefficienti binomiali finché raggiunge (ovvero ) Ora, calcolando tutti i binomi (ricorrendo all'ausilio delle proprietà del coefficiente binomiale), otteniamo il seguente triangolo: Facciamo le seguenti osservazioni:
OSS 3.1.1. Alle "estremità" del triangolo risulta sempre il numero , in quanto seconda la proprietà 2.,
OSS 3.1.2. Se sono arrivato alla riga , posso ottenere facilmente tutti gli elementi della prossima riga ; infatti . Facendo un'interpretazione "geometrica" si può dire che se sono alla riga , allora ottengo l'elemento di questa riga sulla colonna sommando degli elementi che già conosciamo prima; ovvero .
Questi sono gli elementi che stanno al di "sopra" e "sopra e sinistra" dell'elemento che vogliamo conoscere.
ESEMPIO 3.1.2.1. Per esempio ho e voglio ottenere gli elementi della riga ; in questo caso metto alle "estremità" i numeri (OSS 3.1.1.), poi per calcolare (ovviamente ) sommo l'elemento che sta sopra con quello che sta sopra e a sinistra. Quindi otteniamo OSS. 3.1.3. Il matematico B. Pascal nota il seguente nel suo trattato "Traité du triangle arithmétique": che se prendiamo una riga pari , allora il numero "centrale" della riga è uguale alla sommatoria di tutti i quadrati degli elementi della riga .
Ovvero ESEMPIO 3.1.3.1. Prendiamo la riga , ove l'elemento "centrale" è individuato con e la riga , Ora vediamo di sommare tutti gli elementi al quadrato:

4. TEOREMA DEL BINOMIO (o di Newton)

Il triangolo di Tartaglia è una costruzione matematica molto importante, in quanto essa può essere sfruttata per sviluppare la potenza di un binomio in grazie al teorema del Binomio (o di Newton)
TEOREMA 1. Siano (volendo anche in ), sia , allora DIM. Si dimostra questo teorema per induzione.
1. Verificare che è vera per : 2. Verificare che, supponendo allora è vera. 3. Adesso "estraiamo" il primo elemento dalla prima sommatoria e l'ultimo elemento dall'altra sommatoria. 4. Effettuiamo un "trucco" alla seconda sommatoria, ovvero quella di porre (e pertanto ) e poi di porre , che è possibile in quanto è una variabile muta. 5. E riferendosi alla sommatoria presente nell'uguaglianza, se prendiamo e , allora e quindi possiamo "rintegrarli" nella sommatoria come l'elemento -esimo e -esimo, ottenendo che è ciò che volevamo ottenere. Quindi il teorema è stato così dimostrato.

4.1. ESEMPI SUL TEOREMA DEL BINOMIO

ESEMPIO 4.1.1. Vogliamo calcolare .
Otteniamo innanzitutto lo sviluppo di secondo il teorema binomiale: Ora costruiamo il triangolo di Tartaglia fino alla 6-esima riga, secondo le regole notate in 3. Costruzione del triangolo di Tartaglia: Ora sfruttiamo questo triangolo per poter sostituire tutti i coefficienti binomiali nella forma sviluppata appena scritta. ESEMPIO 4.1.2. Calcolare .
Si può risolvere questo problema in due modi:

  1. Se (per definizione) consideriamo il coefficiente binomiale come la cardinalità delle combinazioni di un insieme (ove ) , ovvero il numero degli sottoinsiemi di con elementi, allora possiamo considerare questo problema come il seguente: "qual è la cardinalità di tutti gli sottoinsiemi di (quindi da a elementi)?"; dai risultati della Teoria degli Insiemi, sappiamo immediatamente che la risposta è .
  2. Oppure possiamo semplicemente usare il teorema del binomio; ovvero ponendo , abbiamo dandoci così immediatamente la risposta.

ESEMPIO 4.1.3. Calcolare Se consideriamo il 3.1. Triangolo di Tartaglia, viene che la risposta intuitiva è , in quanto le righe dispari sono simmetriche; quindi "dividendo" quella riga, abbiamo un "lato" positivo e negativo, che sommandoli otteniamo .
Tuttavia questa risposta non è abbastanza rigorosa per essere considerata; infatti per avere una giustificazione più sicura, si deve usare il teorema del binomio nel seguente modo.
Siano , ovvero